En gestion de projet : recherche du chemin critique

Un problème comparable à la recherche du plus court chemin que nous avons résolue avec l'algorithme de Dijkstra est la recherche du plus long chemin, qui est un problème classique en
recherche opérationnelle, la durée minimale d’un projet étant donnée par celle du plus long chemin dans le graphe des tâches à exécuter (le « chemin critique »).

Pour que cette recherche du plus long chemin converge, il faut qu’il n’y ait pas de cycles (on obtiendrait des chemins arbitrairement longs en les répétant indéfiniment), condition qui dans la pratique d’un projet est automatiquement satisfaite (si le plombier doit attendre que l’électricien ait fini pour commencer et si l’électricien doit aussi attendre que le plombier ait fini pour commencer, le chantier devient impossible !).